/*
 * @Author: your name
 * @Date: 2021-10-04 18:06:19
 * @LastEditTime: 2021-10-04 18:23:05
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \luogu\1.2排序\P1177\4main.cpp
 */
#include<iostream>
#include<stack>
using namespace std;

// #define MAX_LENGTH 1000000010
#define MAX_LENGTH 100

//分区
int partition(int a[],int l,int r);
//非递归实现
void quickSort(int a[],int l,int r);

int main(){
    int a[MAX_LENGTH];
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    quickSort(a,0,n-1);
    for(int i=0; i<n; i++){
        cout << a[i] << " ";
    }
    return 0;
}
int partition(int a[],int l,int r)
{
    int pivot = a[l];
    while(l < r){
        //右边大数移到左边
        while(l < r && a[r] >= pivot) r--;
        a[l] = a[r]; 
        //左边小数移到右边
        while(l < r && a[l] <= pivot) l++;
        a[r] = a[l];
    }
    a[l] = pivot;
    return l;
}
void quickSort(int a[],int l,int r)
{
    stack<int> s;
    if(l < r){
        int mid = partition(a,l,r);
        //左右入栈 先小后大
        if(l < mid-1){
            s.push(l);
            s.push(mid-1);
        }
        if(r > mid+1){
            s.push(mid+1);
            s.push(r);
        }
        //出栈,继续partition
        while(!s.empty()){
            //出栈
            r = s.top(); //大数
            s.pop();
            l = s.top(); //小数
            s.pop();
            //partition
            mid = partition(a,l,r);
            //入栈
            if(l < mid-1){
                s.push(l);
                s.push(mid-1);
            }
            if(r > mid+1){
                s.push(mid+1);
                s.push(r);
            }
        }
    }
}